package algocasts;

import java.util.Stack;

public class P68_SortArrayToBST {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) return null;
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }

    // Time :O(n)  Space:O(log(n))
    public TreeNode SortArrayToBST_Recursive(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    private class Item {
        TreeNode parent;
        int start, end;
        boolean isLeft;

        public Item(TreeNode parent, int start, int end, boolean isLeft) {
            this.parent = parent;
            this.start = start;
            this.end = end;
            this.isLeft = isLeft;
        }
    }

    // Time: O(n)  Space: O(n)
    public TreeNode SortArrayToBST_Iterative(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        Stack<Item> stack = new Stack<>();
        TreeNode dummy = new TreeNode(0);
        stack.push(new Item(dummy, 0, nums.length - 1, true));
        while (!stack.isEmpty()) {
            Item item = stack.pop();
            if (item.start <= item.end) {
                int mid = item.start + (item.end - item.start) / 2;
                TreeNode child = new TreeNode(nums[mid]);
                if (item.isLeft) item.parent.left = child;
                else item.parent.right = child;

                stack.push(new Item(child, item.start, mid - 1, true));
                stack.push(new Item(child, mid + 1, item.end, false));
            }
        }
        return dummy.left;
    }
}
